package com.fh.binarysearch;

/**
 * T4.寻找两个有序数组的中位数
 * @author: fuhao
 * @date: 2025/10/14 21:41
 */
public class T4FindMedianSortedArrays {

    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // 确保nums1是较短的数组，优化性能
            if (nums1.length > nums2.length) {
                return findMedianSortedArrays(nums2, nums1);
            }

            int m = nums1.length, n = nums2.length;
            int totalLeft = (m + n + 1) / 2; // 左半部分应有的元素数量

            // 在nums1上执行二分查找
            int left = 0, right = m;
            while (left < right) {
                int i = left + (right - left + 1) / 2; // nums1的分割点
                int j = totalLeft - i; // nums2的分割点

                if (nums1[i - 1] > nums2[j]) {
                    // 分割点需要左移
                    right = i - 1;
                } else {
                    left = i;
                }
            }

            int i = left, j = totalLeft - i;

            // 处理边界情况，确定四个关键值
            int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if ((m + n) % 2 == 1) {
                return Math.max(nums1LeftMax, nums2LeftMax);
            } else {
                return (Math.max(nums1LeftMax, nums2LeftMax) +
                        Math.min(nums1RightMin, nums2RightMin)) / 2.0;
            }
        }
    }
}
